#include "list.h"
#include "string.h"
#include <stdio.h>
#include "logger.h"

//the list must be inited
//O(1)
int IsEmpty(List L)
{
    return L->Next == NULL;
}

//if P is the last node of L
//O(1)
int IsLast(Position P, List L)
{
    return P->Next == NULL;
}

//return the first position of X
//O(N)
Position Find(ElementType X, List L)
{
    //从第一个元素开始
    Position P = L->Next;

    while (P != NULL && P->Element != X)
    {
        P = P->Next;
    }

    return P;
}

//查找元素的上一个元素，方便插入和删除
//O(N)
Position FindPrevious(ElementType X, List L)
{
    Position P = L;
    while (P->Next != NULL && P->Next->Element != X)
    {
        P = P->Next;
    }
    return P;
}

//O(N)
void Delete(ElementType X, List L)
{
    Position P, Tmp;
    P = FindPrevious(X, L);
    if (!IsLast(P, L))
    {
        Tmp = P->Next;
        P->Next = Tmp->Next;
        free(Tmp);
    }
    printf("%d\n", P->Element);
}

//将元素插入到指定位置。虽然L没有用到，但是基于面向对象的思想，因为此操作是对L执行的，所以传参同样需要指定L。
//O(1)
void Insert(ElementType X, List L, Position P)
{
    Position Tmp = malloc(sizeof(*Tmp));
    if (Tmp == NULL)
    {
        FatalError("malloc error!");
    }

    Tmp->Element = X;
    Tmp->Next = P->Next;
    P->Next = Tmp;
}

void MakeEmpty(List L)
{
    Position P, Tmp;
    P = L->Next;
    L->Next = NULL;
    while (!P)
    {
        Tmp = P->Next;
        free(P);
        P = Tmp;
    }
}

//释放整张表的空间
//O(N)
void Release(List L)
{
    MakeEmpty(L);
    free(L);
}

void Print(List L)
{
    Position P = L->Next;
    while (P)
    {
        printf("%d ", P->Element);
        P = P->Next;
    }
    printf("\n");
}